Bộ Nội vụ được thành lập ngay sau khi Việt Nam Dân chủ Cộng hòa ra đời. Ngày 28/8/1945, Võ Nguyên Giáp được bổ nhiệm làm Bộ trưởng Bộ Nội vụ, lãnh đạo Bộ và công việc tổ chức chính quyền, an ninh, nội trị trong thời kỳ Việt Nam mới giành lại được độc lập.

Trong thời gian đầu Bộ trưởng Bộ Nội vụ là người có quyền lực thứ 2 trong Chính phủ, được phép ký một loạt sắc lệnh quan trọng quy định những việc như thiết quân luật, quy định về Quốc kỳ, mở cuộc Tổng tuyển cử,... dưới danh nghĩa "Thay mặt Chủ tịch Chính phủ lâm thời, Bộ trưởng Bộ Nội vụ".

Ngày 21/02/1946, Chính phủ đã ban hành Sắc lệnh thành lập Việt Nam Công an vụ trực thuộc Bộ Nội vụ. Ban đầu có nhiệm vụ: Tìm kiếm và tập trung các tin tức và tài liệu liên quan đến sự an toàn của quốc gia ở cả trong và ngoài nước; đề nghị và thi hành các phương pháp đề phòng những hành động của người Việt Nam hay người nước ngoài gây rối trật tự an ninh của đất nước; điều tra những hành động trái phép và truy tìm can phạm gửi lên toà án xét xử.

Ngày 29/05/1946, Chủ tịch Hồ Chí Minh đã ký Sắc lệnh cử Bộ trưởng Bộ Nội vụ Huỳnh Thúc Kháng sẽ thay người ký những công văn thường ngày của Chính phủ và Chủ tọa Hội đồng Chính phủ. Trong Chính phủ Liên hiệp kháng chiến thì người đứng đầu hai bộ quan trọng: Bộ Nội vụ và Bộ Quốc phòng, phải là các nhân sĩ trung lập. Bộ trưởng Bộ Nội vụ Huỳnh Thúc Kháng thuộc vai trò nhân sĩ trung lập.

Ngày 16/02/1953, Chủ tịch Hồ Chí Minh ký Sắc lệnh thành lập Thứ Bộ công an thuộc Bộ Nội vụ. Theo Sắc lệnh này, Việt Nam Công an vụ thuộc Bộ Nội vụ được đổi lại thành Thứ Bộ công an. Lãnh đạo Thứ Bộ công an là một Thứ trưởng. Tháng 8/1953, Hội đồng Chính phủ quyết định đổi Thứ Bộ công an thành Bộ Công an. Từ đây Bộ Công an tách ra khỏi Bộ Nội vụ, trở thành một Bộ của Chính phủ. Từ đây về sau Bộ Nội vụ hoạt động đi vào ổn định với nhiệm vụ chính về tổ chức xây dựng bộ máy chính quyền và công tác cán bộ, công chức.

Tại kỳ họp thứ nhất Quốc hội khóa V (tháng 6/1975), Quốc hội đã quyết định hợp nhất hai Bộ Công an và Bộ Nội vụ thành Bộ Nội vụ. Bộ mới tuy vẫn được gọi là Bộ Nội vụ nhưng lại chỉ làm nhiệm vụ cảnh sát, an ninh quốc gia và phòng cháy, chữa cháy. Ban Tổ chức của Chính phủ được thành lập với vai trò của Bộ Nội vụ cũ. Đứng đầu Ban Tổ chức của Chính phủ là Trưởng ban là thành viên trực thuộc Chính phủ.

Ngày 07/05/1990, Ban Tổ chức của Chính phủ được đổi tên thành Ban Tổ chức Cán bộ của Chính phủ. Chức vụ lãnh đạo Ban ngang với Bộ trưởng, còn được gọi Bộ trưởng, Trưởng ban Tổ chức Cán bộ của Chính phủ. Đến ngày 05/08/2002, Quốc hội khóa XI (kỳ họp thứ nhất) quyết định đổi tên Ban Tổ chức Cán bộ Chính phủ thành Bộ Nội vụ. Đứng đầu Bộ Nội vụ là Bộ trưởng, Bộ trưởng đầu tiên sau tái lập là Đỗ Quang Trung.